

import java.util.Iterator;
import java.util.NoSuchElementException;

public class RandomizedQueue<Item> implements Iterable<Item> {
	private Item[] dataArray;
	private int size;

	public RandomizedQueue(){
		dataArray = (Item[])new Object[2];
	}

	private void expandDataArrayIfRequired(){
		if(size==0){
			dataArray = (Item[])new Object[2];
		}
		else if(size>=dataArray.length){
			Item[] temp = dataArray;
			dataArray = (Item[])new Object[size<<1];

			for(int i=0;i<size;i++){
				dataArray[i] = temp[i];
			}
		}
	}
	private void checkNull(Item item){
		if(null==item){
			throw new NullPointerException();
		}
	}

	private void shrinkDataArrayIfRequired(){
	
		if(size==(dataArray.length>>2)){
			Item[] temp = dataArray;
			dataArray = (Item[])new Object[dataArray.length>>1];

			for(int i=0;i<size;i++){
				dataArray[i] = temp[i];
			}
		}
	}

	private void checkEmpty(){
		if(isEmpty())
			throw new NoSuchElementException("EMpty");
	}
	public boolean isEmpty(){
		return size==0;
	}
	public void enqueue(Item item){
		checkNull(item);
		expandDataArrayIfRequired();
		dataArray[size++] = item;
	}
	public Item dequeue() {
		checkEmpty();
		int returnIdx = StdRandom.uniform(size);
		Item returnElement = dataArray[returnIdx];
		dataArray[returnIdx]=dataArray[size-1];
		size--;
		dataArray[size]=null;
		shrinkDataArrayIfRequired();
		return returnElement;
	}
	public Item sample(){
		checkEmpty();
		return dataArray[StdRandom.uniform(size)];
	}
	public int size(){
		return size;
	}
	public Iterator<Item> iterator() {
		return new RandomIterator();
	}
	private RandomizedQueue<Item> cloneQueue(){
		RandomizedQueue<Item> queue = new RandomizedQueue<Item>();
		Item[] clonedArray = (Item[]) new Object[dataArray.length];
		for(int i=0; i<dataArray.length;i++){
			clonedArray[i] = dataArray[i];
		}
		queue.dataArray = clonedArray;
		queue.size = size;
		return queue;
	}
	public static void main(String[] args){
		RandomizedQueue<String> test = new RandomizedQueue<String>();
		test.enqueue("test0");
		test.enqueue("test1");
		test.enqueue("test2");
		System.out.println(test.dequeue());
		//System.out.println(test.sample());
		test.enqueue("test3");
		test.enqueue("test4");
		test.enqueue("test5");
		/*	for(String str:test){
			System.out.println(str);
		}
		System.out.println("Again");
		for(String str:test){
			System.out.println(str);
		}*/
		System.out.println(test.dequeue());
		//System.out.println(test.sample());
		System.out.println(test.dequeue());
		System.out.println(test.dequeue());
		System.out.println(test.dequeue());
		System.out.println(test.dequeue());
		try{
			System.out.println(test.dequeue());
		}catch(RuntimeException e){

		}
		test.enqueue("aaa");
		System.out.println(test.dequeue());
		System.out.println(test.size());
		System.out.println("Again");

	}

	private class RandomIterator implements Iterator<Item>{
		private RandomizedQueue<Item> queue;
		public RandomIterator(){
			this.queue = cloneQueue();
		}

		public boolean hasNext() {
			return queue.size!=0;
		}

		public Item next() {
			return queue.dequeue();
		}

		public void remove() {
			throw new UnsupportedOperationException("Unsupported");
		}

	}

}
